"""
【练习】斐波那契数列
编写一个Python程序，使用递归算法，生成并输出斐波那契数列的前n项，其中n是用户指定的正整数。
斐波那契数列，又称黄金分割数列，
指的是：1、1、2、3、5、8、13、21、34....从第三个数开始，每个数字都是前两个数字之和
"""

# 方法一:循环实现
def fibonacci_1(n):
    l = [1, 1]
    for i in range(2, n):
        res = l[i-2] + l[i-1]
        l.append(res)
    return l


# fibonacci_1(8)


# 方法二:递归算法
def fibonacci_2(n):
    if n <= 0:
        return []
    elif n == 1:
        return [1]
    if n == 2:
        return [1, 1]
    else:
        res = fibonacci_2(n-1)
        res.append(res[-1]+res[-2])
        return res


def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 计算斐波那契数列的第 10 项
n = 10
fib_result = fibonacci(n)
print(f"斐波那契数列的第 {n} 项为：{fib_result}")

